
from itertools import combinations
from collections import defaultdict
def apriori(data, min_support):

    def generate_candidates(prev_freq_itemsets, k):
        candidates = set()
        itemsets = list(prev_freq_itemsets)
        for i in range(len(itemsets)):
            for j in range(i + 1, len(itemsets)):
                union = itemsets[i] | itemsets[j]
                if len(union) == k:
                    candidates.add(union)
        return candidates

    # 1
    item_support = defaultdict(int)
    for transaction in data:
        for item in transaction:
            item_support[frozenset([item])] += 1

    frequent_itemsets = {k: v for k, v in item_support.items() if v >= min_support}
    all_frequent_itemsets = dict(frequent_itemsets)

    k = 2

    while frequent_itemsets:
        # 2
        candidates = generate_candidates(frequent_itemsets.keys(), k)

        # 3
        candidate_support = defaultdict(int)
        for transaction in data:
            for candidate in candidates:
                if candidate.issubset(transaction):
                    candidate_support[candidate] += 1

        # 4
        frequent_itemsets = {k: v for k, v in candidate_support.items() if v >= min_support}
        all_frequent_itemsets.update(frequent_itemsets)
        k += 1

    return all_frequent_itemsets

transactions = [
    {'milk', 'bread', 'butter'},
    {'beer', 'bread', 'butter', 'milk'},
    {'milk', 'bread'},
    {'beer', 'bread'},
    {'milk', 'bread', 'butter', 'beer'}
]

min_support_threshold = 2
frequent_itemsets = apriori(transactions, min_support_threshold)

print("Frequent Itemsets and their Supports:")
for itemset, support in frequent_itemsets.items():
    print(f"{set(itemset)}: {support}")